/*
 * @lc app=leetcode.cn id=977 lang=cpp
 *
 * [977] 有序数组的平方
 */

// @lc code=start
class Solution
{
public:
    vector<int> sortedSquares(vector<int> &nums)
    {
        //暴力解法是Onlgn
        //双指针解法 两个指针分别指向前后
        //因为最大值要么在前要么在后面
        vector<int> res(nums.size(), 0);
        int left = 0;
        int right = nums.size() - 1;
        int k = nums.size() - 1;
        while (left <= right)
        {
            if (nums[right] * nums[right] > nums[left] * nums[left])
            {
                res[k] = nums[right] * nums[right];
                right--;
            }
            else
            {
                res[k] = nums[left] * nums[left];
                left++;
            }
            k--;
        }
        return res;
    }
};
// @lc code=end
